package A一周刷爆LeetCode.B基础提升.D滑动窗口与单调栈结构;

import java.util.LinkedList;

/**
 * 求滑动窗口所有最大值
 */
public class Code01_SlidingWindowMaxArray {

    public static void main(String[] args) {
        int[] nums = {1, -1};
        int k = 1;
        int[] maxWindow = getMaxWindow(nums, k);
        for (int i : maxWindow) {
            System.out.println(i);
        }
    }

    public static int[] getMaxWindow(int[] nums, int k) {
        if (null == nums || nums.length == 0 || k == 0) {
            return null;
        }
        int[] result = new int[nums.length - k + 1];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (null != list.peekLast() && nums[list.peekLast()] <= nums[i]) {
                list.pollLast();
            }
            list.add(i);
            if (list.peekFirst() == i - k) {
                list.pollFirst();
            }
            if (i >= k - 1) {
                result[i - k + 1] = nums[list.peekFirst()];
            }
        }
        return result;
    }

}
